const UnionFind = require('./dataStruct/unionFind').UnionFind;
const common = require('./base/common');

/**
 * 1579. 保证图可完全遍历
 * 
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var maxNumEdgesToRemove = function(n, edges) {
    // 排序，先处理公用边
    edges.sort((a,b) => b[0] - a[0]);

    // 并查集构建树
    let alice = new UnionFind(n + 1), 
        bob = new UnionFind(n + 1), 
        deleted = 0,
        aliceEdge = 0,
        bobEdge = 0;
    for(let i=0; i < edges.length; ++i) {
        let type = edges[i][0], 
            a = edges[i][1], 
            b = edges[i][2],
            processes = type == 3? [alice, bob]: (type == 1? [alice]: [bob]),
            canDelete = false;
        for(let process of processes) {
            if(!(canDelete = process.connected(a, b))) {
                process.union(a, b);
                if(process == alice) aliceEdge++;
                if(process == bob) bobEdge++;
            }
        }
        deleted += canDelete? 1: 0;
    }

    return aliceEdge != n - 1 || bobEdge != n - 1? -1: deleted;
};

common.testing([
    [4, [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]],
    [4, [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]],
    [4, [[3,2,3],[1,1,2],[2,3,4]]]
], [2, 0, -1])((x) => maxNumEdgesToRemove(x[0], x[1]));